package 快速排序;

import java.util.Arrays;

public class 挖坑法 {

    public static int partition(int[] arr,int low,int high) {
        //high 用来找比基准值小的
        //low  用来找比基准值大的
        int tmp=arr[low];
        while (low<high) {
            while (low<high && arr[high]>=tmp) {
                high--;
            }
            arr[low]=arr[high];//比基准值小的往前放

            while (low<high && arr[low]<=tmp) {
                low++;
            }
            arr[high]=arr[low];//比基准值大的往后放
        }
        arr[low]=tmp;
        return low;
    }

    public static void quickSortChild(int[] arr,int start,int end) {
        //递归
        if (start>=end) {
            return;
        }

        if (end-start+1>100) {
            insertSort2(arr,start,end);
            return;//当前区间经过直接插入排序后，当前区间就不用再递归了，直接返回即可
        }

        //基于三数取中的优化
        int mid=(start+end)/2;
        selectPivotMedianOfThree(arr,start,end,mid);
        //基准值的选择已经优化完成

        int pivot=partition(arr,start,end);
        quickSortChild(arr,start,pivot-1);
        quickSortChild(arr,pivot+1,end);
    }

    public static void quickSort(int[] arr) {
        quickSortChild(arr,0,arr.length-1);
    }

    //优化快排——三数取中作为基准值
    public static void selectPivotMedianOfThree(int[] arr,int start,int end,int mid) {
        //最终 arr[mid] <= arr[start] <= arr[end]，arr[start]作为基准值pivot

        //保证 arr[start] >= arr[mid]
        if (arr[start] < arr[mid]) {
            swap(arr,start,mid);
        }

        //再保证 arr[start] <= arr[end]
        if (arr[start] > arr[end]) {
            swap(arr,start,end);
        }

        //最后保证 arr[mid] < arr[end]
        if (arr[mid] > arr[end]) {
            swap(arr,mid,end);
        }

    }
    public static void swap(int[] arr,int a,int b) {
        int tmp=arr[a];
        arr[a]=arr[b];
        arr[b]=tmp;
    }

    //优化——直接插入
    public static void insertSort2(int[] arr,int start,int end) {
        for (int i = start+1; i <end+1; i++) {
            int j=i-1;
            int tmp=arr[i];

            for (; j >=start; j--) {
                if (arr[j]>tmp) {//一个稳定的排序，可以实现为不稳定的排序 arr[j]>=tmp
                    arr[j+1]=arr[j];
                }else {
                    break;
                }
            }
            arr[j+1]=tmp;
        }
    }

    public static void main(String[] args) {
        int[] arr={12,5,9,34,6,8,33,56,89,0,7,4,22,55,77};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));

    }

}
